/*
 * @lc app=leetcode.cn id=76 lang=javascript
 *
 * [76] 最小覆盖子串
 */
// @lc code=start
/**
 * 1. 用双指针维护一个滑动窗口，用来剪切子串
 * 2. 移动右指针直到找到包含T的子串；然后移动左指针尽可能减少包含T的字串；记录最小子串
 * 3. 当无法减少时，移动右指针，重复2；
 * 4. 比较所有的结果子串，得出最小结果即可
 * 注意点：
 * 如何判断是否满足，可以使用Map结构存储目标子字符串元素，值为字符在目标子字符串中应该出现的次数；为0时代表符合条件了
 * 循环结束条件：
 * 外层处理资源字符串的结束：右指针抵达最末尾
 * 内层寻找最小子字符串的结束：左指针右移动，直到【字符在目标子字符串中应该出现的次数】非0时则跳出
 *
 * 时间复杂度：M + N
 * 空间复杂度：M
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  let l = 0;
  let r = 0;
  let needType = 0; // 目标子字符串中非重复字符应出现个数长度 长度为0时代表符合要求
  let need = new Map();
  let res = ""; // 结果字符串
  for (const c of t) {
    need.set(c, need.has(c) ? need.get(c) + 1 : 1);
  }
  needType = need.size;
  while (r < s.length) {
    const c = s[r];
    // 当前处理字符属于目标子字符串
    if (need.has(c)) {
      // 将【应该出现次数】-1
      need.set(c, need.get(c) - 1);
      // 如果此字符【应该出现次数】为0，则将【目标子字符串中非重复字符长度】-1
      if (need.get(c) === 0) {
        needType -= 1;
      }
    }
    // 如果目标子字符串中非重复字符长度为0，代表符合要求，则开始尝试缩短长度，即左指针右移动
    while (needType === 0) {
      // 记录下当前符合条件的子串
      const newRes = s.substring(l, r + 1);
      // 如果比当前结果子串短，则更新
      if (!res || newRes.length < res.length) {
        res = newRes;
      }
      const c2 = s[l];
      // 当前左指针元素如果也在目标字符中
      if (need.has(c2)) {
        // 则将当前字符【应该出现次数】+1
        need.set(c2, need.get(c2) + 1);
        // 如果当前元素应出现次数等于1 则【目标子字符串中非重复字符应出现个数长度】+1
        if (need.get(c2) === 1) {
          needType += 1;
        }
      }
      // 左指针右移动
      l += 1;
    }
    // 右指针右移动
    r += 1;
  }
  return res;
};
// minWindow("ADOBECODEBANC", "ABC");
// @lc code=end
